package com.kehao.leetcode.jzoffer;

import org.junit.Test;

import java.math.BigInteger;
import java.util.*;
import java.util.stream.Collectors;

/**
 * @author Kehao.Chen
 * @version 1.0
 * @date 2022/7/5 14:29
 */
public class JZSolution048 {

    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        Map<BigInteger, Integer> map = new TreeMap<>();
        dfs(root, map, BigInteger.valueOf(0));
        String result = map.entrySet().stream().map(entry -> entry.getKey() + ":" + entry.getValue()).collect(Collectors.joining(","));
        return result;
    }

    private void dfs(TreeNode root, Map<BigInteger, Integer> map, BigInteger i) {
        if (root == null) return;
        map.put(i, root.val);
        dfs(root.left, map, i.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1)));
        dfs(root.right, map, i.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(2)));
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.isEmpty()) return null;
        if(!data.contains(",")) return new TreeNode(Integer.parseInt(data.split(":")[1]));
        String[] split = data.split(",");
        Map<BigInteger, TreeNode> map = new TreeMap<>();
        Arrays.stream(split).forEach(str -> {
            String[] strArray = str.split(":");
            map.put(new BigInteger(strArray[0]), new TreeNode(Integer.parseInt(strArray[1])));
        });
        for (BigInteger index : map.keySet()) {
            map.get(index).left = map.get(index.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(1)));
            map.get(index).right = map.get(index.multiply(BigInteger.valueOf(2)).add(BigInteger.valueOf(2)));
        }
        return map.get(BigInteger.ZERO);
    }


    @Test
    public void test01() {
        TreeNode root = new TreeNode(1);
        TreeNode p = root;
        for (int i = 2; i < 10; i++) {
            p.right= new TreeNode(i);
            p = p.right;
        }


        String serialize = serialize(root);
        System.out.println(serialize);

        TreeNode deserialize = deserialize(serialize);
        System.out.println(deserialize);
    }


}
